import com.sun.deploy.security.SelectableSecurityManager;
import sun.font.DelegatingShape;

import java.util.Arrays;

public class MyPriorityQueue {
    public int[] elem;
    public int usesize;

    public MyPriorityQueue(){
        this.elem=new int[10];
    }

    public void newarr(int []arr){
        for (int i=0;i<arr.length;i++){
            this.elem[i]=arr[i];
            usesize++;
        }
    }
    public void da(){
        for ( int panter=(usesize-1)/2;panter>=0;panter--) {
            int childer=panter*2+1;
            while (childer < usesize ) {
                if (childer + 1 < usesize && elem[childer] < elem[childer + 1]) {
                    childer++;

                }
                if (elem[panter] < elem[childer]) {
                    jiao(elem, panter, childer);
                    panter = childer;
                    childer = panter * 2 + 1;
                }
                else {
                    break;
                }
            }
        }
    }
    public void add(int val){
        if(iffill()){
           elem=Arrays.copyOf(elem,elem.length*2);
        }
        elem[usesize]=val;
        usesize++;
        int childer=usesize-1;
        uppoff(childer);
        }
    public void uppoff(int childer){//向上调整
        while (childer!=0) {
            int parter = (childer - 1) / 2;
            if (elem[parter] < elem[childer]) {
                jiao(elem, parter, childer);
                childer = parter;
                parter = (childer - 1) / 2;
            }
        }
    }

    public boolean iffill(){
        return usesize==elem.length;
    }
    public void datle(){//删除首元素
        if (ifnull()){
            return;
        }
            jiao(elem,0,usesize-1);
            uppdown(0,usesize);//逻辑删除，下一次添加数据的时候被覆盖 所以可以替换后直接初始化
            elem[usesize]=0;
    }
    public void uppdown(int panter,int usesize){//向下调整
        int childer=panter*2+1;
        while (childer < usesize ) {
            if (childer + 1 < usesize && elem[childer] < elem[childer + 1]) {
                childer++;

            }
            if (elem[panter] < elem[childer]) {
                jiao(elem, panter, childer);
                panter = childer;
                childer = panter * 2 + 1;
            }
            else {
                break;
            }
        }
    }
    public boolean ifnull(){
        return usesize==0;
    }
    public void jiao(int []elem,int ret1,int ret2){
        int temp=elem[ret1];
        elem[ret1]=elem[ret2];
        elem[ret2]=temp;
    }
    public void paxun(){
        int end=usesize-1;
        while (end>0){
            jiao(elem,0,end);
            uppdown(0,end);
            end--;
        }
    }

    @Override
    public String toString() {
        return "MyPriorityQueue{" +
                "elem=" + Arrays.toString(elem) +
                ", usesize=" + usesize +
                '}';
    }


    public static void main(String[] args) {
        int []arr={27,15,19,18,28,34,65,49,25,37};
        MyPriorityQueue myPriorityQueue=new MyPriorityQueue();
        myPriorityQueue.newarr(arr);
        System.out.println(myPriorityQueue.toString());
        System.out.println("以大堆排序后:");
        myPriorityQueue.da();
        System.out.println(myPriorityQueue.toString());
        System.out.println("倒叙排序");
        myPriorityQueue.paxun();
        System.out.println(myPriorityQueue.toString());
        System.out.println("添加新元素后面的大堆排序");
        myPriorityQueue.add(88);
        System.out.println(myPriorityQueue.toString());
        System.out.println("删除元素后的堆排序");
        myPriorityQueue.datle();
        System.out.println(myPriorityQueue.toString());
        myPriorityQueue.add(100);
        System.out.println(myPriorityQueue.toString());
    }
}
